package day_2023_4_to_7;

/**
 * @author haomin
 * @date 2023/04/23 21:21
 **/
public class Day4_23_Num1105 {
    class Solution {
        public int minHeightShelves(int[][] books, int shelfWidth) {
            int N = books.length;
            // 把N本书放成一排，产生N+1个间隔
            // dp[i]表示到第i个间隔，之前的i-1本书的最小高度
            int []dp = new int[N+1];
            for(int i=1;i<=N;i++){
                int curWidth=0;
                int max = 0;
                dp[i] = Integer.MAX_VALUE;
                for(int j=i-1;j>=0;j--){
                    // 将第j个间隔-第i个间隔中间的书放在一层，判断宽度是否小于书架
                    curWidth += books[j][0];
                    if(curWidth>shelfWidth) break;
                    // 该层的高度是这些书里最高的
                    max = Math.max(max,books[j][1]);
                    // 总高度为第j个间隔前的高度+本层
                    // 比较这样分层是否最优
                    dp[i] = Math.min(dp[i],dp[j]+max);
                }
            }
            return dp[N];
        }
    }
}